In a storage device, Garbage Collection (GC) is a memory management technique used for reclaiming memory that is no longer used. The memory so reclaimed returns to the free memory pool (pages) that can be used for future write operations. Data is written into a storage device in terms of pages and erased in terms of memory blocks. Moreover, existing data cannot be read and written back at the same memory location. Therefore, in order to claim a stale page in the storage device, the whole memory block that includes the stale page needs to be erased.
The existing arts of garbage collection use a garbage collector component in the storage device. The garbage collector component selects a memory block having lowest number of valid pages for deletion. The garbage collector component copies valid pages of the selected memory block to a free memory block and deletes the selected memory block, thereby recycling the selected memory block.
However, the existing arts initiate the garbage collection operation only in response to a write operation on the storage device and/or when the controller in the storage device determines that only a limited number of free memory blocks are left in the storage device. As a result, the writing operation on the storage device gets delayed and the user experience gets impacted. Also, a frequent initiation of the garbage collection operation may also overload the system by consuming more processor cycles. Further, a memory block selected for deletion may also comprise a number of free pages. Deleting a memory block having the free pages will not free any memory space since the page is already free. Hence, it is necessary to consider the number of free pages in a memory block before selecting it for deletion.
The issues mainly faced in performing garbage collection in a storage device are determining the number of free pages in the memory block and recycling a memory block having minimum number of free pages, minimum number of valid pages and maximum number of invalid pages.